# file: optimized_heap.py
import random
import time
from typing import List
import heapq

class Solution:
    def find1(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]

    def findHeap(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            if len(heap) < k:
                heapq.heappush(heap, num)
            elif num > heap[0]:  # 堆顶是最小值
                heapq.heapreplace(heap, num)
        return heap[0]  # 返回堆顶即为第k大的数

def run():
    sizes = [1000, 5000, 10000, 20000, 25000, 50000, 100000]
    sorttimes = []
    heaptimes = []
    k_ratio = 0.1  # k值设为数组大小的10%
    sol = Solution()

    print(f"{'数组规模':<10} {'排序方法(ms)':<15} {'堆方法(ms)':<15} {'性能比较'}")
    print("-" * 55)
    
    for n in sizes:
        k = max(1, int(n * k_ratio))
        nums = [random.randint(0, 100000) for _ in range(n)]

        # 测试排序方法
        start_time = time.time()
        sol.find1(nums.copy(), k)
        time1 = (time.time() - start_time) * 1000
        sorttimes.append(time1)

        # 测试堆方法
        start_time = time.time()
        sol.findHeap(nums.copy(), k)
        time2 = (time.time() - start_time) * 1000
        heaptimes.append(time2)
        # 比较结果
        if time1 > time2:
            comparison = "堆方法更快"
        else:
            comparison = "排序方法更快"

        print(f"{n:<10} {time1:<15.2f} {time2:<15.2f} {comparison}")

if __name__ == "__main__":
    run()